'''
https://leetcode.cn/problems/insert-into-a-sorted-circular-linked-list
'''


# Definition for a Node.
class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return f'Node({self.val})'


class Solution:
    def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
        newnode = Node(insertVal)
        if not head:
            newnode.next = newnode
            return newnode

        pre, cur = head, head.next
        while True:
            if pre.val <= insertVal <= cur.val:
                # 1) 中间插入
                pre.next = newnode
                newnode.next = cur
                return head
            elif pre.val > cur.val and (insertVal >= pre.val or insertVal <= cur.val):
                # 2) 拐点，且新节点是极值
                pre.next = newnode
                newnode.next = cur
                return head
            pre, cur = cur, cur.next
            if pre == head:     # 最多1次遍历
                break

        # 3) 既没能在中间插入， 又没在拐点插入
        #    首先插入值肯定是极值，
        #    然后链表没有拐点
        pre.next = newnode
        newnode.next = cur
        return head


head = Node(3)
node1 = Node(5)
node2 = Node(6)
node3 = Node(3)
head.next = node1
node1.next = node2
# node2.next = head
node2.next = node3
node3.next = head
insertval = 3
Solution().insert(head, insertval)
